/**
////////////////////////////////////////////////////////////////////////////////
//                                                                            // 
//  Copyright (c) 2013 Santiago Benito Rebollo. Eclipse Public License - v 1.0//
//  @author Santiago Benito Rebollo.                                          // 
//  santiago.benito.rebollo@gmail.com                                         //
//                                                                            //  
////////////////////////////////////////////////////////////////////////////////
//                                                                            //
// THE ACCOMPANYING PROGRAM IS PROVIDED UNDER THE TERMS OF THIS ECLIPSE PUBLIC// 
// LICENSE ("AGREEMENT"). ANY USE, REPRODUCTION OR DISTRIBUTION OF THE PROGRAM//
// CONSTITUTES RECIPIENT'S ACCEPTANCE OF THIS AGREEMENT.                      //
//                                                                            //
// A Contributor may choose to distribute the Program in object code form     //
// under its own license agreement, provided that:                            //
//                                                                            //
// a) it complies with the terms and conditions of this Agreement; and        //
// b) its license agreement:                                                  //
//                                                                            //
// i) effectively disclaims on behalf of all Contributors all warranties and  //
// conditions, express and implied, including warranties or conditions of     //  
// title and non-infringement, and implied warranties or conditions of        //
// merchantability and fitness for a particular purpose;                      //
// ii) effectively excludes on behalf of all Contributors all liability for   //
// damages, including direct, indirect, special, incidental and consequential //
// damages, such as lost profits;                                             //
// iii) states that any provisions which differ from this Agreement are       //
// offered by that Contributor alone and not by any other party; and          //
// iv) states that source code for the Program is available from such         //
// Contributor, and informs licensees how to obtain it in a reasonable        //
// manner on or through a medium customarily used for software exchange.      //
//                                                                            //
////////////////////////////////////////////////////////////////////////////////
 */

/**
CmIdentification
////////////////////////////////////////////////////////////////////////////////
// Version History:
// [Rev d.d dd Mmm yyyy hh:mm:ss    <logComment>]
$Log: Dijkstra.java,v $
////////////////////////////////////////////////////////////////////////////////
 */

package com.chago.fastrecado;


import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

/**
 * This class has the Dijkstra algorithm to calculate paths between vertexes.
 * 
 * @author Santiago Benito Rebollo
 * @author santiago.benito.rebollo@gmail.com
 */
public class Dijkstra {
	
    /**
     * This method compute the path using distance or time as weight in the edge between vertex.
     * 
     * @param Vertice source
     * @param boolean booDistanceTime (true for DISTANCE, false for TIME)
     * @throws none Exception
     * @pre source != null
     * @post $none
     */		
    public static void computePaths(Vertice source,boolean booDistanceTime)
    {
        source.minDistance = 0.;
        PriorityQueue<Vertice> vertexQueue = new PriorityQueue<Vertice>();
      	vertexQueue.add(source);

	while (!vertexQueue.isEmpty()) {
	    Vertice u = vertexQueue.poll();

            // Visit each edge exiting u
            for (Arista e : u.adjacencies)
            {
                Vertice v = e.target;
                double weight = 0;
                if (booDistanceTime==true) {
                	weight = e.getDistance();
                }
                else{
                	weight = e.getTime();
                }
                
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                	vertexQueue.remove(v);
                	v.minDistance = distanceThroughU ;
                	v.previous = u;
                	vertexQueue.add(v);
                } // end if
            }// end for
        }// end while
    }// end computePaths

    /**
     * This method obtain the shortest path for the vertex targeted
     * 
     * @param Vertice target
     * @throws none Exception
     * @pre target != null
     * @post $none
     */
    public static List<Vertice> getShortestPathTo(Vertice target)
    {
        List<Vertice> path = new ArrayList<Vertice>();
        for (Vertice vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);
        Collections.reverse(path);
        return path;
    }
		
}
